package arithmetic.demo19;


import java.util.Arrays;

/**
 * 题目： 贪心 + 二分_最长递增子序列
 */

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int ret = 0;
        int[]  tmp = new int[n];
        // 遍历
        for(int i =0; i< n; i++) {
            int num = nums[i];
            // 分情况
            if(ret == 0 || num  > tmp[ret-1]) {
                // 如果大于边界值就直接尾插
                tmp[ret] = nums[i];
                ret++;
            }  else {
                // 如果在其中就进行二分
                int left = 0, right = ret - 1;
                while(left < right) {
                    int mid =   left +  ((right - left) / 2);
                    if(tmp[mid] < num) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }

                tmp[left] = num;
            }
        }

        return ret;
    }
}

class Test {

    public static void main(String[] args) {
        int[] nums = {10,9,2,5,3,7,101,18};
        Solution solution = new Solution();
        System.out.println(solution.lengthOfLIS(nums));
    }
}


/**
 * 题目: 动态规划_地下城游戏
 */

class Solution2 {
    public int calculateMinimumHP(int[][] nums) {
        int raw = nums.length, col = nums[0].length;
        int[][] dp = new int[raw + 1][col + 1];


        // 初始化
        for(int i = 0; i <= raw ; i++) {
            Arrays.fill(dp[i],200_0000);
        }

        dp[raw -1][col] = dp[raw][col -1] = 1;

        // 进行状态转移
        for(int i = raw - 1 ; i >= 0 ; i--) {
            for( int j = col -1 ; j >= 0 ; j--) {
                dp[i][j] =  Math.min(dp[i+1][j] - nums[i][j] , dp[i][j+1] - nums[i][j]);
                if(dp[i][j] <= 0) dp[i][j] = 1;
            }
        }


        return dp[0][0];
    }
}


class Test1 {
    public static void main(String[] args) {
        Solution2 s  = new Solution2();
        int[][] nums ={{-3,5}};
        System.out.println(s.calculateMinimumHP(nums));
    }
}




